{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Recommendation Systems Colab",
      "version": "0.3.2",
      "provenance": [],
      "collapsed_sections": [
        "9EjQt_o9Xf_L"
      ],
      "toc_visible": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "accelerator": "GPU"
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9EjQt_o9Xf_L",
        "colab_type": "text"
      },
      "source": [
        "#### Copyright 2018 Google LLC."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "oXzTW-CnXf_Q",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
        "# you may not use this file except in compliance with the License.\n",
        "# You may obtain a copy of the License at\n",
        "#\n",
        "# https://www.apache.org/licenses/LICENSE-2.0\n",
        "#\n",
        "# Unless required by applicable law or agreed to in writing, software\n",
        "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
        "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
        "# See the License for the specific language governing permissions and\n",
        "# limitations under the License."
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "k0IFBGCx8_im"
      },
      "source": [
        "# Recommendation Systems with TensorFlow\n",
        "\n",
        "This Colab notebook complements the course on [Recommendation Systems](https://developers.google.com/machine-learning/recommendation/). Specifically, we'll be using matrix factorization to learn user and movie embeddings.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Le0Z54X68_iq"
      },
      "source": [
        "# Introduction\n",
        "\n",
        "We will create a movie recommendation system based on the [MovieLens](https://movielens.org/) dataset available [here](http://grouplens.org/datasets/movielens/).  The data consists of movies ratings (on a scale of 1 to 5).\n",
        "\n",
        "## Outline\n",
        "  1. Exploring the MovieLens Data (10 minutes)\n",
        "  1. Preliminaries (25 minutes)\n",
        "  1. Training a matrix factorization model (15 minutes)\n",
        "  1. Inspecting the Embeddings (15 minutes)\n",
        "  1. Regularization in matrix factorization (15 minutes)\n",
        "  1. Softmax model training (30 minutes)\n",
        "\n",
        "## Setup\n",
        "\n",
        "Let's get started by importing the required packages."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "8vRUh2Mzo4s1",
        "colab": {}
      },
      "source": [
        "# @title Imports (run this cell)\n",
        "from __future__ import print_function\n",
        "\n",
        "import numpy as np\n",
        "import pandas as pd\n",
        "import collections\n",
        "from mpl_toolkits.mplot3d import Axes3D\n",
        "from IPython import display\n",
        "from matplotlib import pyplot as plt\n",
        "import sklearn\n",
        "import sklearn.manifold\n",
        "import tensorflow.compat.v1 as tf\n",
        "tf.disable_v2_behavior()\n",
        "tf.logging.set_verbosity(tf.logging.ERROR)\n",
        "\n",
        "# Add some convenience functions to Pandas DataFrame.\n",
        "pd.options.display.max_rows = 10\n",
        "pd.options.display.float_format = '{:.3f}'.format\n",
        "def mask(df, key, function):\n",
        "  \"\"\"Returns a filtered dataframe, by applying function to key\"\"\"\n",
        "  return df[function(df[key])]\n",
        "\n",
        "def flatten_cols(df):\n",
        "  df.columns = [' '.join(col).strip() for col in df.columns.values]\n",
        "  return df\n",
        "\n",
        "pd.DataFrame.mask = mask\n",
        "pd.DataFrame.flatten_cols = flatten_cols\n",
        "\n",
        "# Install Altair and activate its colab renderer.\n",
        "print(\"Installing Altair...\")\n",
        "!pip install git+git://github.com/altair-viz/altair.git\n",
        "import altair as alt\n",
        "alt.data_transformers.enable('default', max_rows=None)\n",
        "alt.renderers.enable('colab')\n",
        "print(\"Done installing Altair.\")\n",
        "\n",
        "# Install spreadsheets and import authentication module.\n",
        "USER_RATINGS = False\n",
        "!pip install --upgrade -q gspread\n",
        "from google.colab import auth\n",
        "import gspread\n",
        "from oauth2client.client import GoogleCredentials"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "KhAVFaqCo4s5"
      },
      "source": [
        "We then download the MovieLens Data, and create DataFrames containing movies, users, and ratings."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "O3bcgduFo4s6",
        "colab": {}
      },
      "source": [
        "# @title Load the MovieLens data (run this cell).\n",
        "\n",
        "# Download MovieLens data.\n",
        "print(\"Downloading movielens data...\")\n",
        "from urllib.request import urlretrieve\n",
        "import zipfile\n",
        "\n",
        "urlretrieve(\"http://files.grouplens.org/datasets/movielens/ml-100k.zip\", \"movielens.zip\")\n",
        "zip_ref = zipfile.ZipFile('movielens.zip', \"r\")\n",
        "zip_ref.extractall()\n",
        "print(\"Done. Dataset contains:\")\n",
        "print(zip_ref.read('ml-100k/u.info'))\n",
        "\n",
        "# Load each data set (users, movies, and ratings).\n",
        "users_cols = ['user_id', 'age', 'sex', 'occupation', 'zip_code']\n",
        "users = pd.read_csv(\n",
        "    'ml-100k/u.user', sep='|', names=users_cols, encoding='latin-1')\n",
        "\n",
        "ratings_cols = ['user_id', 'movie_id', 'rating', 'unix_timestamp']\n",
        "ratings = pd.read_csv(\n",
        "    'ml-100k/u.data', sep='\\t', names=ratings_cols, encoding='latin-1')\n",
        "\n",
        "# The movies file contains a binary feature for each genre.\n",
        "genre_cols = [\n",
        "    \"genre_unknown\", \"Action\", \"Adventure\", \"Animation\", \"Children\", \"Comedy\",\n",
        "    \"Crime\", \"Documentary\", \"Drama\", \"Fantasy\", \"Film-Noir\", \"Horror\",\n",
        "    \"Musical\", \"Mystery\", \"Romance\", \"Sci-Fi\", \"Thriller\", \"War\", \"Western\"\n",
        "]\n",
        "movies_cols = [\n",
        "    'movie_id', 'title', 'release_date', \"video_release_date\", \"imdb_url\"\n",
        "] + genre_cols\n",
        "movies = pd.read_csv(\n",
        "    'ml-100k/u.item', sep='|', names=movies_cols, encoding='latin-1')\n",
        "\n",
        "# Since the ids start at 1, we shift them to start at 0.\n",
        "users[\"user_id\"] = users[\"user_id\"].apply(lambda x: str(x-1))\n",
        "movies[\"movie_id\"] = movies[\"movie_id\"].apply(lambda x: str(x-1))\n",
        "movies[\"year\"] = movies['release_date'].apply(lambda x: str(x).split('-')[-1])\n",
        "ratings[\"movie_id\"] = ratings[\"movie_id\"].apply(lambda x: str(x-1))\n",
        "ratings[\"user_id\"] = ratings[\"user_id\"].apply(lambda x: str(x-1))\n",
        "ratings[\"rating\"] = ratings[\"rating\"].apply(lambda x: float(x))\n",
        "\n",
        "# Compute the number of movies to which a genre is assigned.\n",
        "genre_occurences = movies[genre_cols].sum().to_dict()\n",
        "\n",
        "# Since some movies can belong to more than one genre, we create different\n",
        "# 'genre' columns as follows:\n",
        "# - all_genres: all the active genres of the movie.\n",
        "# - genre: randomly sampled from the active genres.\n",
        "def mark_genres(movies, genres):\n",
        "  def get_random_genre(gs):\n",
        "    active = [genre for genre, g in zip(genres, gs) if g==1]\n",
        "    if len(active) == 0:\n",
        "      return 'Other'\n",
        "    return np.random.choice(active)\n",
        "  def get_all_genres(gs):\n",
        "    active = [genre for genre, g in zip(genres, gs) if g==1]\n",
        "    if len(active) == 0:\n",
        "      return 'Other'\n",
        "    return '-'.join(active)\n",
        "  movies['genre'] = [\n",
        "      get_random_genre(gs) for gs in zip(*[movies[genre] for genre in genres])]\n",
        "  movies['all_genres'] = [\n",
        "      get_all_genres(gs) for gs in zip(*[movies[genre] for genre in genres])]\n",
        "\n",
        "mark_genres(movies, genre_cols)\n",
        "\n",
        "# Create one merged DataFrame containing all the movielens data.\n",
        "movielens = ratings.merge(movies, on='movie_id').merge(users, on='user_id')\n",
        "\n",
        "# Utility to split the data into training and test sets.\n",
        "def split_dataframe(df, holdout_fraction=0.1):\n",
        "  \"\"\"Splits a DataFrame into training and test sets.\n",
        "  Args:\n",
        "    df: a dataframe.\n",
        "    holdout_fraction: fraction of dataframe rows to use in the test set.\n",
        "  Returns:\n",
        "    train: dataframe for training\n",
        "    test: dataframe for testing\n",
        "  \"\"\"\n",
        "  test = df.sample(frac=holdout_fraction, replace=False)\n",
        "  train = df[~df.index.isin(test.index)]\n",
        "  return train, test"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "bfhOILgfo4s8"
      },
      "source": [
        "# I. Exploring the Movielens Data\n",
        "Before we dive into model building, let's inspect our MovieLens dataset. It is usually helpful to understand the statistics of the dataset."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "EoB8Drqwo4s-"
      },
      "source": [
        "### Users\n",
        "We start by printing some basic statistics describing the numeric user features."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "k-IRqWato4s-",
        "colab": {}
      },
      "source": [
        "users.describe()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "h3nZ1ARho4tC"
      },
      "source": [
        "We can also print some basic statistics describing the categorical user features"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "jFGxSmTGo4tD",
        "colab": {}
      },
      "source": [
        "users.describe(include=[np.object])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "CH2_gW3Oo4tF"
      },
      "source": [
        "We can also create histograms to further understand the distribution of the users. We use Altair to create an interactive chart."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "ffkqaK_zo4tF",
        "colab": {}
      },
      "source": [
        "# @title Altair visualization code (run this cell)\n",
        "# The following functions are used to generate interactive Altair charts.\n",
        "# We will display histograms of the data, sliced by a given attribute.\n",
        "\n",
        "# Create filters to be used to slice the data.\n",
        "occupation_filter = alt.selection_multi(fields=[\"occupation\"])\n",
        "occupation_chart = alt.Chart().mark_bar().encode(\n",
        "    x=\"count()\",\n",
        "    y=alt.Y(\"occupation:N\"),\n",
        "    color=alt.condition(\n",
        "        occupation_filter,\n",
        "        alt.Color(\"occupation:N\", scale=alt.Scale(scheme='category20')),\n",
        "        alt.value(\"lightgray\")),\n",
        ").properties(width=300, height=300, selection=occupation_filter)\n",
        "\n",
        "# A function that generates a histogram of filtered data.\n",
        "def filtered_hist(field, label, filter):\n",
        "  \"\"\"Creates a layered chart of histograms.\n",
        "  The first layer (light gray) contains the histogram of the full data, and the\n",
        "  second contains the histogram of the filtered data.\n",
        "  Args:\n",
        "    field: the field for which to generate the histogram.\n",
        "    label: String label of the histogram.\n",
        "    filter: an alt.Selection object to be used to filter the data.\n",
        "  \"\"\"\n",
        "  base = alt.Chart().mark_bar().encode(\n",
        "      x=alt.X(field, bin=alt.Bin(maxbins=10), title=label),\n",
        "      y=\"count()\",\n",
        "  ).properties(\n",
        "      width=300,\n",
        "  )\n",
        "  return alt.layer(\n",
        "      base.transform_filter(filter),\n",
        "      base.encode(color=alt.value('lightgray'), opacity=alt.value(.7)),\n",
        "  ).resolve_scale(y='independent')\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "D93Jn4Pao4tH"
      },
      "source": [
        "Next, we look at the distribution of ratings per user. Clicking on an occupation in the right chart will filter the data by that occupation. The corresponding histogram is shown in blue, and superimposed with the histogram for the whole data (in light gray). You can use SHIFT+click to select multiple subsets.\n",
        "\n",
        "What do you observe, and how might this affect the recommendations?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cmzAwTCRWhLY",
        "colab_type": "text"
      },
      "source": [
        ""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "x4ahcH2do4tI",
        "colab": {}
      },
      "source": [
        "users_ratings = (\n",
        "    ratings\n",
        "    .groupby('user_id', as_index=False)\n",
        "    .agg({'rating': ['count', 'mean']})\n",
        "    .flatten_cols()\n",
        "    .merge(users, on='user_id')\n",
        ")\n",
        "\n",
        "# Create a chart for the count, and one for the mean.\n",
        "alt.hconcat(\n",
        "    filtered_hist('rating count', '# ratings / user', occupation_filter),\n",
        "    filtered_hist('rating mean', 'mean user rating', occupation_filter),\n",
        "    occupation_chart,\n",
        "    data=users_ratings)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "pmC6wykPo4tK"
      },
      "source": [
        "### Movies\n",
        "\n",
        "It is also useful to look at information about the movies and their ratings."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "tCdPQRsso4tL",
        "colab": {}
      },
      "source": [
        "movies_ratings = movies.merge(\n",
        "    ratings\n",
        "    .groupby('movie_id', as_index=False)\n",
        "    .agg({'rating': ['count', 'mean']})\n",
        "    .flatten_cols(),\n",
        "    on='movie_id')\n",
        "\n",
        "genre_filter = alt.selection_multi(fields=['genre'])\n",
        "genre_chart = alt.Chart().mark_bar().encode(\n",
        "    x=\"count()\",\n",
        "    y=alt.Y('genre'),\n",
        "    color=alt.condition(\n",
        "        genre_filter,\n",
        "        alt.Color(\"genre:N\"),\n",
        "        alt.value('lightgray'))\n",
        ").properties(height=300, selection=genre_filter)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "NH9QQNr6o4tO",
        "colab": {}
      },
      "source": [
        "(movies_ratings[['title', 'rating count', 'rating mean']]\n",
        " .sort_values('rating count', ascending=False)\n",
        " .head(10))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "xNb5Lz1oo4tP",
        "colab": {}
      },
      "source": [
        "(movies_ratings[['title', 'rating count', 'rating mean']]\n",
        " .mask('rating count', lambda x: x > 20)\n",
        " .sort_values('rating mean', ascending=False)\n",
        " .head(10))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "kW_WRQyDo4tR"
      },
      "source": [
        "Finally, the last chart shows the distribution of the number of ratings and average rating."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "z8wxFfV8o4tR",
        "colab": {}
      },
      "source": [
        "# Display the number of ratings and average rating per movie.\n",
        "alt.hconcat(\n",
        "    filtered_hist('rating count', '# ratings / movie', genre_filter),\n",
        "    filtered_hist('rating mean', 'mean movie rating', genre_filter),\n",
        "    genre_chart,\n",
        "    data=movies_ratings)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "WEhp-q31o4tS"
      },
      "source": [
        "# II. Preliminaries\n",
        "\n",
        "Our goal is to factorize the ratings matrix $A$ into the product of a user embedding matrix $U$ and movie embedding matrix $V$, such that $A \\approx UV^\\top$ with\n",
        "$U = \\begin{bmatrix} u_{1} \\\\ \\hline \\vdots \\\\ \\hline u_{N} \\end{bmatrix}$ and\n",
        "$V = \\begin{bmatrix} v_{1} \\\\ \\hline \\vdots \\\\ \\hline v_{M} \\end{bmatrix}$.\n",
        "\n",
        "Here\n",
        "- $N$ is the number of users,\n",
        "- $M$ is the number of movies,\n",
        "- $A_{ij}$ is the rating of the $j$th movies by the $i$th user,\n",
        "- each row $U_i$ is a $d$-dimensional vector (embedding) representing user $i$,\n",
        "- each row $V_j$ is a $d$-dimensional vector (embedding) representing movie $j$,\n",
        "- the prediction of the model for the $(i, j)$ pair is the dot product $\\langle U_i, V_j \\rangle$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "yMYZw_Yco4tT"
      },
      "source": [
        "## Sparse Representation of the Rating Matrix\n",
        "\n",
        "The rating matrix could be very large and, in general, most of the entries are unobserved, since a given user will only rate a small subset of movies. For effcient representation, we will use a [tf.SparseTensor](https://www.tensorflow.org/api_docs/python/tf/SparseTensor). A `SparseTensor` uses three tensors to represent the matrix: `tf.SparseTensor(indices, values, dense_shape)` represents a tensor, where a value $A_{ij} = a$ is encoded by setting `indices[k] = [i, j]` and `values[k] = a`. The last tensor `dense_shape` is used to specify the shape of the full underlying matrix.\n",
        "\n",
        "#### Toy example\n",
        "Assume we have $2$ users and $4$ movies. Our toy ratings dataframe has three ratings,\n",
        "\n",
        "user\\_id | movie\\_id | rating\n",
        "--:|--:|--:\n",
        "0 | 0 | 5.0\n",
        "0 | 1 | 3.0\n",
        "1 | 3 | 1.0\n",
        "\n",
        "The corresponding rating matrix is\n",
        "\n",
        "$$\n",
        "A =\n",
        "\\begin{bmatrix}\n",
        "5.0 & 3.0 & 0 & 0 \\\\\n",
        "0   &   0 & 0 & 1.0\n",
        "\\end{bmatrix}\n",
        "$$\n",
        "\n",
        "And the SparseTensor representation is,\n",
        "```python\n",
        "SparseTensor(\n",
        "  indices=[[0, 0], [0, 1], [1,3]],\n",
        "  values=[5.0, 3.0, 1.0],\n",
        "  dense_shape=[2, 4])\n",
        "```\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "vBNijwXuo4tU"
      },
      "source": [
        "### Exercise 1: Build a tf.SparseTensor representation of the Rating Matrix.\n",
        "\n",
        "In this exercise, we'll write a function that maps from our `ratings` DataFrame to a `tf.SparseTensor`.\n",
        "\n",
        "Hint: you can select the values of a given column of a Dataframe `df` using `df['column_name'].values`."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "dmVu6NVpo4tU",
        "colab": {}
      },
      "source": [
        "def build_rating_sparse_tensor(ratings_df):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings_df: a pd.DataFrame with `user_id`, `movie_id` and `rating` columns.\n",
        "  Returns:\n",
        "    A tf.SparseTensor representing the ratings matrix.\n",
        "  \"\"\"\n",
        "  # ========================= Complete this section ============================\n",
        "  # indices =\n",
        "  # values =\n",
        "  # ============================================================================\n",
        "\n",
        "  return tf.SparseTensor(\n",
        "      indices=indices,\n",
        "      values=values,\n",
        "      dense_shape=[users.shape[0], movies.shape[0]])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "lwgUGTSmo4tW",
        "colab": {}
      },
      "source": [
        "#@title Solution\n",
        "def build_rating_sparse_tensor(ratings_df):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings_df: a pd.DataFrame with `user_id`, `movie_id` and `rating` columns.\n",
        "  Returns:\n",
        "    a tf.SparseTensor representing the ratings matrix.\n",
        "  \"\"\"\n",
        "  indices = ratings_df[['user_id', 'movie_id']].values\n",
        "  values = ratings_df['rating'].values\n",
        "  return tf.SparseTensor(\n",
        "      indices=indices,\n",
        "      values=values,\n",
        "      dense_shape=[users.shape[0], movies.shape[0]])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "8k9CSOH5o4tX"
      },
      "source": [
        "## Calculating the error\n",
        "\n",
        "The model approximates the ratings matrix $A$ by a low-rank product $UV^\\top$. We need a way to measure the approximation error. We'll start by using the Mean Squared Error of observed entries only (we will revisit this later). It is defined as\n",
        "\n",
        "$$\n",
        "\\begin{align*}\n",
        "\\text{MSE}(A, UV^\\top)\n",
        "&= \\frac{1}{|\\Omega|}\\sum_{(i, j) \\in\\Omega}{( A_{ij} - (UV^\\top)_{ij})^2} \\\\\n",
        "&= \\frac{1}{|\\Omega|}\\sum_{(i, j) \\in\\Omega}{( A_{ij} - \\langle U_i, V_j\\rangle)^2}\n",
        "\\end{align*}\n",
        "$$\n",
        "where $\\Omega$ is the set of observed ratings, and $|\\Omega|$ is the cardinality of $\\Omega$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "KI1Ft-I7o4tX"
      },
      "source": [
        "### Exercise 2: Mean Squared Error\n",
        "\n",
        "Write a TensorFlow function that takes a sparse rating matrix $A$ and the two embedding matrices $U, V$ and returns the mean squared error $\\text{MSE}(A, UV^\\top)$.\n",
        "\n",
        "Hints:\n",
        "  * in this section, we only consider observed entries when calculating the loss.\n",
        "  * a `SparseTensor` `sp_x` is a tuple of three Tensors: `sp_x.indices`, `sp_x.values` and `sp_x.dense_shape`.\n",
        "  * you may find [`tf.gather_nd`](https://www.tensorflow.org/api_docs/python/tf/gather_nd) and  [`tf.losses.mean_squared_error`](https://www.tensorflow.org/api_docs/python/tf/losses/mean_squared_error) helpful."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "9GhqKwpQo4tZ",
        "colab": {}
      },
      "source": [
        "def sparse_mean_square_error(sparse_ratings, user_embeddings, movie_embeddings):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    sparse_ratings: A SparseTensor rating matrix, of dense_shape [N, M]\n",
        "    user_embeddings: A dense Tensor U of shape [N, k] where k is the embedding\n",
        "      dimension, such that U_i is the embedding of user i.\n",
        "    movie_embeddings: A dense Tensor V of shape [M, k] where k is the embedding\n",
        "      dimension, such that V_j is the embedding of movie j.\n",
        "  Returns:\n",
        "    A scalar Tensor representing the MSE between the true ratings and the\n",
        "      model's predictions.\n",
        "  \"\"\"\n",
        "  # ========================= Complete this section ============================\n",
        "  # loss =\n",
        "  # ============================================================================\n",
        "  return loss"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "p43zJDN7o4ta",
        "colab": {}
      },
      "source": [
        "#@title Solution\n",
        "def sparse_mean_square_error(sparse_ratings, user_embeddings, movie_embeddings):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    sparse_ratings: A SparseTensor rating matrix, of dense_shape [N, M]\n",
        "    user_embeddings: A dense Tensor U of shape [N, k] where k is the embedding\n",
        "      dimension, such that U_i is the embedding of user i.\n",
        "    movie_embeddings: A dense Tensor V of shape [M, k] where k is the embedding\n",
        "      dimension, such that V_j is the embedding of movie j.\n",
        "  Returns:\n",
        "    A scalar Tensor representing the MSE between the true ratings and the\n",
        "      model's predictions.\n",
        "  \"\"\"\n",
        "  predictions = tf.gather_nd(\n",
        "      tf.matmul(user_embeddings, movie_embeddings, transpose_b=True),\n",
        "      sparse_ratings.indices)\n",
        "  loss = tf.losses.mean_squared_error(sparse_ratings.values, predictions)\n",
        "  return loss"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "IrteGTFgo4td"
      },
      "source": [
        "Note: One approach is to compute the full prediction matrix $UV^\\top$, then gather the entries corresponding to the observed pairs. The memory cost of this approach is $O(NM)$. For the MovieLens dataset, this is fine, as the dense $N \\times M$ matrix is small enough to fit in memory ($N = 943$, $M = 1682$).\n",
        "\n",
        "Another approach (given in the alternate solution below) is to only gather the embeddings of the observed pairs, then compute their dot products. The memory cost is $O(|\\Omega| d)$ where $d$ is the embedding dimension. In our case, $|\\Omega| = 10^5$, and the embedding dimension is on the order of $10$, so the memory cost of both methods is comparable. But when the number of users or movies is much larger, the first approach becomes infeasible."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "6Z0m3dL88Uxd",
        "colab_type": "code",
        "cellView": "both",
        "colab": {}
      },
      "source": [
        "#@title Alternate Solution\n",
        "def sparse_mean_square_error(sparse_ratings, user_embeddings, movie_embeddings):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    sparse_ratings: A SparseTensor rating matrix, of dense_shape [N, M]\n",
        "    user_embeddings: A dense Tensor U of shape [N, k] where k is the embedding\n",
        "      dimension, such that U_i is the embedding of user i.\n",
        "    movie_embeddings: A dense Tensor V of shape [M, k] where k is the embedding\n",
        "      dimension, such that V_j is the embedding of movie j.\n",
        "  Returns:\n",
        "    A scalar Tensor representing the MSE between the true ratings and the\n",
        "      model's predictions.\n",
        "  \"\"\"\n",
        "  predictions = tf.reduce_sum(\n",
        "      tf.gather(user_embeddings, sparse_ratings.indices[:, 0]) *\n",
        "      tf.gather(movie_embeddings, sparse_ratings.indices[:, 1]),\n",
        "      axis=1)\n",
        "  loss = tf.losses.mean_squared_error(sparse_ratings.values, predictions)\n",
        "  return loss"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "X0X56mAlo4tf"
      },
      "source": [
        "### Exercise 3 (Optional): adding your own ratings to the data set"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "o8VazvWLo4tf"
      },
      "source": [
        "You have the option to add your own ratings to the data set. If you choose to do so, you will be able to see recommendations for yourself.\n",
        "\n",
        "Start by checking the box below. Running the next cell will authenticate you to your google Drive account, and create a spreadsheet, that contains all movie titles in column 'A'. Follow the link to the spreadsheet and take 3 minutes to rate some of the movies. Your ratings should be entered in column 'B'."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "ILiSj-x6o4tf",
        "colab": {}
      },
      "source": [
        "USER_RATINGS = True #@param {type:\"boolean\"}"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "TOVDyYHgo4th",
        "colab": {}
      },
      "source": [
        "# @title Run to create a spreadsheet, then use it to enter your ratings.\n",
        "# Authenticate user.\n",
        "if USER_RATINGS:\n",
        "  auth.authenticate_user()\n",
        "  gc = gspread.authorize(GoogleCredentials.get_application_default())\n",
        "  # Create the spreadsheet and print a link to it.\n",
        "  try:\n",
        "    sh = gc.open('MovieLens-test')\n",
        "  except(gspread.SpreadsheetNotFound):\n",
        "    sh = gc.create('MovieLens-test')\n",
        "\n",
        "  worksheet = sh.sheet1\n",
        "  titles = movies['title'].values\n",
        "  cell_list = worksheet.range(1, 1, len(titles), 1)\n",
        "  for cell, title in zip(cell_list, titles):\n",
        "    cell.value = title\n",
        "  worksheet.update_cells(cell_list)\n",
        "  print(\"Link to the spreadsheet: \"\n",
        "        \"https://docs.google.com/spreadsheets/d/{}/edit\".format(sh.id))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "WDj7GoEPo4ti"
      },
      "source": [
        "Run the next  cell to load your ratings and add them to the main `ratings` DataFrame."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "Ubuf5ba3o4ti",
        "colab": {}
      },
      "source": [
        "# @title Run to load your ratings.\n",
        "# Load the ratings from the spreadsheet and create a DataFrame.\n",
        "if USER_RATINGS:\n",
        "  my_ratings = pd.DataFrame.from_records(worksheet.get_all_values()).reset_index()\n",
        "  my_ratings = my_ratings[my_ratings[1] != '']\n",
        "  my_ratings = pd.DataFrame({\n",
        "      'user_id': \"943\",\n",
        "      'movie_id': list(map(str, my_ratings['index'])),\n",
        "      'rating': list(map(float, my_ratings[1])),\n",
        "  })\n",
        "  # Remove previous ratings.\n",
        "  ratings = ratings[ratings.user_id != \"943\"]\n",
        "  # Add new ratings.\n",
        "  ratings = ratings.append(my_ratings, ignore_index=True)\n",
        "  # Add new user to the users DataFrame.\n",
        "  if users.shape[0] == 943:\n",
        "    users = users.append(users.iloc[942], ignore_index=True)\n",
        "    users[\"user_id\"][943] = \"943\"\n",
        "  print(\"Added your %d ratings; you have great taste!\" % len(my_ratings))\n",
        "  ratings[ratings.user_id==\"943\"].merge(movies[['movie_id', 'title']])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "eSfW6SwIo4tk"
      },
      "source": [
        "# III. Training a Matrix Factorization model\n",
        "\n",
        "## CFModel (Collaborative Filtering Model) helper class\n",
        "This is a simple class to train a matrix factorization model using stochastic gradient descent.\n",
        "\n",
        "The class constructor takes\n",
        "- the user embeddings U (a `tf.Variable`).\n",
        "- the movie embeddings V, (a `tf.Variable`).\n",
        "- a loss to optimize (a `tf.Tensor`).\n",
        "- an optional list of metrics dictionaries, each mapping a string (the name of the metric) to a tensor. These are evaluated and plotted during training (e.g. training error and test error).\n",
        "\n",
        "After training, one can access the trained embeddings using the `model.embeddings` dictionary.\n",
        "\n",
        "Example usage:\n",
        "```\n",
        "U_var = ...\n",
        "V_var = ...\n",
        "loss = ...\n",
        "model = CFModel(U_var, V_var, loss)\n",
        "model.train(iterations=100, learning_rate=1.0)\n",
        "user_embeddings = model.embeddings['user_id']\n",
        "movie_embeddings = model.embeddings['movie_id']\n",
        "```\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "6NHoOwido4tk",
        "colab": {}
      },
      "source": [
        "# @title CFModel helper class (run this cell)\n",
        "class CFModel(object):\n",
        "  \"\"\"Simple class that represents a collaborative filtering model\"\"\"\n",
        "  def __init__(self, embedding_vars, loss, metrics=None):\n",
        "    \"\"\"Initializes a CFModel.\n",
        "    Args:\n",
        "      embedding_vars: A dictionary of tf.Variables.\n",
        "      loss: A float Tensor. The loss to optimize.\n",
        "      metrics: optional list of dictionaries of Tensors. The metrics in each\n",
        "        dictionary will be plotted in a separate figure during training.\n",
        "    \"\"\"\n",
        "    self._embedding_vars = embedding_vars\n",
        "    self._loss = loss\n",
        "    self._metrics = metrics\n",
        "    self._embeddings = {k: None for k in embedding_vars}\n",
        "    self._session = None\n",
        "\n",
        "  @property\n",
        "  def embeddings(self):\n",
        "    \"\"\"The embeddings dictionary.\"\"\"\n",
        "    return self._embeddings\n",
        "\n",
        "  def train(self, num_iterations=100, learning_rate=1.0, plot_results=True,\n",
        "            optimizer=tf.train.GradientDescentOptimizer):\n",
        "    \"\"\"Trains the model.\n",
        "    Args:\n",
        "      iterations: number of iterations to run.\n",
        "      learning_rate: optimizer learning rate.\n",
        "      plot_results: whether to plot the results at the end of training.\n",
        "      optimizer: the optimizer to use. Default to GradientDescentOptimizer.\n",
        "    Returns:\n",
        "      The metrics dictionary evaluated at the last iteration.\n",
        "    \"\"\"\n",
        "    with self._loss.graph.as_default():\n",
        "      opt = optimizer(learning_rate)\n",
        "      train_op = opt.minimize(self._loss)\n",
        "      local_init_op = tf.group(\n",
        "          tf.variables_initializer(opt.variables()),\n",
        "          tf.local_variables_initializer())\n",
        "      if self._session is None:\n",
        "        self._session = tf.Session()\n",
        "        with self._session.as_default():\n",
        "          self._session.run(tf.global_variables_initializer())\n",
        "          self._session.run(tf.tables_initializer())\n",
        "          tf.train.start_queue_runners()\n",
        "\n",
        "    with self._session.as_default():\n",
        "      local_init_op.run()\n",
        "      iterations = []\n",
        "      metrics = self._metrics or ({},)\n",
        "      metrics_vals = [collections.defaultdict(list) for _ in self._metrics]\n",
        "\n",
        "      # Train and append results.\n",
        "      for i in range(num_iterations + 1):\n",
        "        _, results = self._session.run((train_op, metrics))\n",
        "        if (i % 10 == 0) or i == num_iterations:\n",
        "          print(\"\\r iteration %d: \" % i + \", \".join(\n",
        "                [\"%s=%f\" % (k, v) for r in results for k, v in r.items()]),\n",
        "                end='')\n",
        "          iterations.append(i)\n",
        "          for metric_val, result in zip(metrics_vals, results):\n",
        "            for k, v in result.items():\n",
        "              metric_val[k].append(v)\n",
        "\n",
        "      for k, v in self._embedding_vars.items():\n",
        "        self._embeddings[k] = v.eval()\n",
        "\n",
        "      if plot_results:\n",
        "        # Plot the metrics.\n",
        "        num_subplots = len(metrics)+1\n",
        "        fig = plt.figure()\n",
        "        fig.set_size_inches(num_subplots*10, 8)\n",
        "        for i, metric_vals in enumerate(metrics_vals):\n",
        "          ax = fig.add_subplot(1, num_subplots, i+1)\n",
        "          for k, v in metric_vals.items():\n",
        "            ax.plot(iterations, v, label=k)\n",
        "          ax.set_xlim([1, num_iterations])\n",
        "          ax.legend()\n",
        "      return results"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "bKis0EyHo4tn"
      },
      "source": [
        "### Exercise 4: Build a Matrix Factorization model and train it\n",
        "\n",
        "Using your `sparse_mean_square_error` function, write a function that builds a `CFModel` by creating the embedding variables and the train and test losses."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "XzaABsnno4tn",
        "colab": {}
      },
      "source": [
        "def build_model(ratings, embedding_dim=3, init_stddev=1.):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings: a DataFrame of the ratings\n",
        "    embedding_dim: the dimension of the embedding vectors.\n",
        "    init_stddev: float, the standard deviation of the random initial embeddings.\n",
        "  Returns:\n",
        "    model: a CFModel.\n",
        "  \"\"\"\n",
        "  # Split the ratings DataFrame into train and test.\n",
        "  train_ratings, test_ratings = split_dataframe(ratings)\n",
        "  # SparseTensor representation of the train and test datasets.\n",
        "  # ========================= Complete this section ============================\n",
        "  # A_train =\n",
        "  # A_test =\n",
        "  # ============================================================================\n",
        "  # Initialize the embeddings using a normal distribution.\n",
        "  U = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[0], embedding_dim], stddev=init_stddev))\n",
        "  V = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[1], embedding_dim], stddev=init_stddev))\n",
        "  # ========================= Complete this section ============================\n",
        "  # train_loss =\n",
        "  # test_loss =\n",
        "  # ============================================================================\n",
        "  metrics = {\n",
        "      'train_error': train_loss,\n",
        "      'test_error': test_loss\n",
        "  }\n",
        "  embeddings = {\n",
        "      \"user_id\": U,\n",
        "      \"movie_id\": V\n",
        "  }\n",
        "  return CFModel(embeddings, train_loss, [metrics])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "M9RxIX_Oo4tp",
        "colab": {}
      },
      "source": [
        "#@title Solution\n",
        "def build_model(ratings, embedding_dim=3, init_stddev=1.):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings: a DataFrame of the ratings\n",
        "    embedding_dim: the dimension of the embedding vectors.\n",
        "    init_stddev: float, the standard deviation of the random initial embeddings.\n",
        "  Returns:\n",
        "    model: a CFModel.\n",
        "  \"\"\"\n",
        "  # Split the ratings DataFrame into train and test.\n",
        "  train_ratings, test_ratings = split_dataframe(ratings)\n",
        "  # SparseTensor representation of the train and test datasets.\n",
        "  A_train = build_rating_sparse_tensor(train_ratings)\n",
        "  A_test = build_rating_sparse_tensor(test_ratings)\n",
        "  # Initialize the embeddings using a normal distribution.\n",
        "  U = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[0], embedding_dim], stddev=init_stddev))\n",
        "  V = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[1], embedding_dim], stddev=init_stddev))\n",
        "  train_loss = sparse_mean_square_error(A_train, U, V)\n",
        "  test_loss = sparse_mean_square_error(A_test, U, V)\n",
        "  metrics = {\n",
        "      'train_error': train_loss,\n",
        "      'test_error': test_loss\n",
        "  }\n",
        "  embeddings = {\n",
        "      \"user_id\": U,\n",
        "      \"movie_id\": V\n",
        "  }\n",
        "  return CFModel(embeddings, train_loss, [metrics])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "mHMTVERDo4ts"
      },
      "source": [
        "Great, now it's time to train the model!\n",
        "\n",
        "Go ahead and run the next cell, trying different parameters (embedding dimension, learning rate, iterations). The training and test errors are plotted at the end of training. You can inspect these values to validate the hyper-parameters.\n",
        "\n",
        "Note: by calling `model.train` again, the model will continue training starting from the current values of the embeddings."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "_BlRIQJYo4tt",
        "colab": {}
      },
      "source": [
        "# Build the CF model and train it.\n",
        "model = build_model(ratings, embedding_dim=30, init_stddev=0.5)\n",
        "model.train(num_iterations=1000, learning_rate=10.)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "-RWinHdno4tu"
      },
      "source": [
        "The movie and user embeddings are also displayed in the right figure. When the embedding dimension is greater than 3, the embeddings are projected on the first 3 dimensions. The next section will have a more detailed look at the embeddings."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "IO1r1A5Xo4tu"
      },
      "source": [
        "# IV. Inspecting the Embeddings\n",
        "\n",
        "In this section, we take a closer look at the learned embeddings, by\n",
        "- computing your recommendations\n",
        "- looking at the nearest neighbors of some movies,\n",
        "- looking at the norms of the movie embeddings,\n",
        "- visualizing the embedding in a projected embedding space."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "8Z3q8xZVo4tw"
      },
      "source": [
        "### Exercise 5: Write a function that computes the scores of the candidates\n",
        "We start by writing a function that, given a query embedding $u \\in \\mathbb R^d$ and item embeddings $V \\in \\mathbb R^{N \\times d}$, computes the item scores.\n",
        "\n",
        "As discussed in the lecture, there are different similarity measures we can use, and these can yield different results. We will compare the following:\n",
        "- dot product: the score of item j is $\\langle u, V_j \\rangle$.\n",
        "- cosine: the score of item j is $\\frac{\\langle u, V_j \\rangle}{\\|u\\|\\|V_j\\|}$.\n",
        "\n",
        "Hints:\n",
        "- you can use [`np.dot`](https://docs.scipy.org/doc/numpy/reference/generated/numpy.dot.html) to compute the product of two np.Arrays.\n",
        "- you can use [`np.linalg.norm`](https://docs.scipy.org/doc/numpy-1.14.0/reference/generated/numpy.linalg.norm.html) to compute the norm of a np.Array."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "lBnrZUspo4tx",
        "colab": {}
      },
      "source": [
        "DOT = 'dot'\n",
        "COSINE = 'cosine'\n",
        "def compute_scores(query_embedding, item_embeddings, measure=DOT):\n",
        "  \"\"\"Computes the scores of the candidates given a query.\n",
        "  Args:\n",
        "    query_embedding: a vector of shape [k], representing the query embedding.\n",
        "    item_embeddings: a matrix of shape [N, k], such that row i is the embedding\n",
        "      of item i.\n",
        "    measure: a string specifying the similarity measure to be used. Can be\n",
        "      either DOT or COSINE.\n",
        "  Returns:\n",
        "    scores: a vector of shape [N], such that scores[i] is the score of item i.\n",
        "  \"\"\"\n",
        "  # ========================= Complete this section ============================\n",
        "  # scores =\n",
        "  # ============================================================================\n",
        "  return scores"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "PqDjkdlFo4t0",
        "colab": {}
      },
      "source": [
        "#@title Solution\n",
        "DOT = 'dot'\n",
        "COSINE = 'cosine'\n",
        "def compute_scores(query_embedding, item_embeddings, measure=DOT):\n",
        "  \"\"\"Computes the scores of the candidates given a query.\n",
        "  Args:\n",
        "    query_embedding: a vector of shape [k], representing the query embedding.\n",
        "    item_embeddings: a matrix of shape [N, k], such that row i is the embedding\n",
        "      of item i.\n",
        "    measure: a string specifying the similarity measure to be used. Can be\n",
        "      either DOT or COSINE.\n",
        "  Returns:\n",
        "    scores: a vector of shape [N], such that scores[i] is the score of item i.\n",
        "  \"\"\"\n",
        "  u = query_embedding\n",
        "  V = item_embeddings\n",
        "  if measure == COSINE:\n",
        "    V = V / np.linalg.norm(V, axis=1, keepdims=True)\n",
        "    u = u / np.linalg.norm(u)\n",
        "  scores = u.dot(V.T)\n",
        "  return scores"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "EDpSY1REo4t1"
      },
      "source": [
        "Equipped with this function, we can compute recommendations, where the query embedding can be either a user embedding or a movie embedding."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "6dSF9U1fo4t2",
        "colab": {}
      },
      "source": [
        "# @title User recommendations and nearest neighbors (run this cell)\n",
        "def user_recommendations(model, measure=DOT, exclude_rated=False, k=6):\n",
        "  if USER_RATINGS:\n",
        "    scores = compute_scores(\n",
        "        model.embeddings[\"user_id\"][943], model.embeddings[\"movie_id\"], measure)\n",
        "    score_key = measure + ' score'\n",
        "    df = pd.DataFrame({\n",
        "        score_key: list(scores),\n",
        "        'movie_id': movies['movie_id'],\n",
        "        'titles': movies['title'],\n",
        "        'genres': movies['all_genres'],\n",
        "    })\n",
        "    if exclude_rated:\n",
        "      # remove movies that are already rated\n",
        "      rated_movies = ratings[ratings.user_id == \"943\"][\"movie_id\"].values\n",
        "      df = df[df.movie_id.apply(lambda movie_id: movie_id not in rated_movies)]\n",
        "    display.display(df.sort_values([score_key], ascending=False).head(k))  \n",
        "\n",
        "def movie_neighbors(model, title_substring, measure=DOT, k=6):\n",
        "  # Search for movie ids that match the given substring.\n",
        "  ids =  movies[movies['title'].str.contains(title_substring)].index.values\n",
        "  titles = movies.iloc[ids]['title'].values\n",
        "  if len(titles) == 0:\n",
        "    raise ValueError(\"Found no movies with title %s\" % title_substring)\n",
        "  print(\"Nearest neighbors of : %s.\" % titles[0])\n",
        "  if len(titles) > 1:\n",
        "    print(\"[Found more than one matching movie. Other candidates: {}]\".format(\n",
        "        \", \".join(titles[1:])))\n",
        "  movie_id = ids[0]\n",
        "  scores = compute_scores(\n",
        "      model.embeddings[\"movie_id\"][movie_id], model.embeddings[\"movie_id\"],\n",
        "      measure)\n",
        "  score_key = measure + ' score'\n",
        "  df = pd.DataFrame({\n",
        "      score_key: list(scores),\n",
        "      'titles': movies['title'],\n",
        "      'genres': movies['all_genres']\n",
        "  })\n",
        "  display.display(df.sort_values([score_key], ascending=False).head(k))"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "iOwtUnJzo4t3"
      },
      "source": [
        "### Your recommendations\n",
        "\n",
        "If you chose to input your recommendations, you can run the next cell to generate recommendations for you."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "efvKEUOPo4t4",
        "colab": {}
      },
      "source": [
        "user_recommendations(model, measure=COSINE, k=5)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "msMJzGF3o4t6"
      },
      "source": [
        "How do the recommendations look?"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "fFaiyCtgo4t6"
      },
      "source": [
        "### Movie Nearest neighbors\n",
        "\n",
        "Let's look at the neareast neighbors for some of the movies."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "ejJHfA-so4t8",
        "colab": {}
      },
      "source": [
        "movie_neighbors(model, \"Aladdin\", DOT)\n",
        "movie_neighbors(model, \"Aladdin\", COSINE)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "JD3X1ua8o4uA"
      },
      "source": [
        "It seems that the quality of learned embeddings may not be very good. This will be addressed in Section V by adding several regularization techniques. First, we will further inspect the embeddings."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "SOxdxqpKo4uB"
      },
      "source": [
        "## Movie Embedding Norm\n",
        "\n",
        "We can also observe that the recommendations with dot-product and cosine are different: with dot-product, the model tends to recommend popular movies. This can be explained by the fact that in matrix factorization models, the norm of the embedding is often correlated with popularity (popular movies have a larger norm), which makes it more likely to recommend more popular items. We can confirm this hypothesis by sorting the movies by their embedding norm, as done in the next cell."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "G_Kko-YxF6YE",
        "colab_type": "code",
        "cellView": "form",
        "colab": {}
      },
      "source": [
        "# @title Embedding Visualization code (run this cell)\n",
        "\n",
        "def movie_embedding_norm(models):\n",
        "  \"\"\"Visualizes the norm and number of ratings of the movie embeddings.\n",
        "  Args:\n",
        "    model: A MFModel object.\n",
        "  \"\"\"\n",
        "  if not isinstance(models, list):\n",
        "    models = [models]\n",
        "  df = pd.DataFrame({\n",
        "      'title': movies['title'],\n",
        "      'genre': movies['genre'],\n",
        "      'num_ratings': movies_ratings['rating count'],\n",
        "  })\n",
        "  charts = []\n",
        "  brush = alt.selection_interval()\n",
        "  for i, model in enumerate(models):\n",
        "    norm_key = 'norm'+str(i)\n",
        "    df[norm_key] = np.linalg.norm(model.embeddings[\"movie_id\"], axis=1)\n",
        "    nearest = alt.selection(\n",
        "        type='single', encodings=['x', 'y'], on='mouseover', nearest=True,\n",
        "        empty='none')\n",
        "    base = alt.Chart().mark_circle().encode(\n",
        "        x='num_ratings',\n",
        "        y=norm_key,\n",
        "        color=alt.condition(brush, alt.value('#4c78a8'), alt.value('lightgray'))\n",
        "    ).properties(\n",
        "        selection=nearest).add_selection(brush)\n",
        "    text = alt.Chart().mark_text(align='center', dx=5, dy=-5).encode(\n",
        "        x='num_ratings', y=norm_key,\n",
        "        text=alt.condition(nearest, 'title', alt.value('')))\n",
        "    charts.append(alt.layer(base, text))\n",
        "  return alt.hconcat(*charts, data=df)\n",
        "\n",
        "def visualize_movie_embeddings(data, x, y):\n",
        "  nearest = alt.selection(\n",
        "      type='single', encodings=['x', 'y'], on='mouseover', nearest=True,\n",
        "      empty='none')\n",
        "  base = alt.Chart().mark_circle().encode(\n",
        "      x=x,\n",
        "      y=y,\n",
        "      color=alt.condition(genre_filter, \"genre\", alt.value(\"whitesmoke\")),\n",
        "  ).properties(\n",
        "      width=600,\n",
        "      height=600,\n",
        "      selection=nearest)\n",
        "  text = alt.Chart().mark_text(align='left', dx=5, dy=-5).encode(\n",
        "      x=x,\n",
        "      y=y,\n",
        "      text=alt.condition(nearest, 'title', alt.value('')))\n",
        "  return alt.hconcat(alt.layer(base, text), genre_chart, data=data)\n",
        "\n",
        "def tsne_movie_embeddings(model):\n",
        "  \"\"\"Visualizes the movie embeddings, projected using t-SNE with Cosine measure.\n",
        "  Args:\n",
        "    model: A MFModel object.\n",
        "  \"\"\"\n",
        "  tsne = sklearn.manifold.TSNE(\n",
        "      n_components=2, perplexity=40, metric='cosine', early_exaggeration=10.0,\n",
        "      init='pca', verbose=True, n_iter=400)\n",
        "\n",
        "  print('Running t-SNE...')\n",
        "  V_proj = tsne.fit_transform(model.embeddings[\"movie_id\"])\n",
        "  movies.loc[:,'x'] = V_proj[:, 0]\n",
        "  movies.loc[:,'y'] = V_proj[:, 1]\n",
        "  return visualize_movie_embeddings(movies, 'x', 'y')"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "SXP_eW-Xo4uD",
        "colab": {}
      },
      "source": [
        "movie_embedding_norm(model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "5o1vQGyIo4uE"
      },
      "source": [
        "Note: Depending on how the model is initialized, you may observe that some niche movies (ones with few ratings) have a high norm, leading to spurious recommendations. This can happen if the embedding of that movie happens to be initialized with a high norm. Then, because the movie has few ratings, it is infrequently updated, and can keep its high norm. This will be alleviated by using regularization.\n",
        "\n",
        "Try changing the value of the hyper-parameter `init_stddev`. One quantity that can be helpful is that the expected norm of a $d$-dimensional vector with entries $\\sim \\mathcal N(0, \\sigma^2)$ is approximatley $\\sigma \\sqrt d$.\n",
        "\n",
        "How does this affect the embedding norm distribution, and the ranking of the top-norm movies?"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2I0FcjkPAoO4",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "#@title Solution\n",
        "model_lowinit = build_model(ratings, embedding_dim=30, init_stddev=0.05)\n",
        "model_lowinit.train(num_iterations=1000, learning_rate=10.)\n",
        "movie_neighbors(model_lowinit, \"Aladdin\", DOT)\n",
        "movie_neighbors(model_lowinit, \"Aladdin\", COSINE)\n",
        "movie_embedding_norm([model, model_lowinit])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "fF6dMP1To4uH"
      },
      "source": [
        "## Embedding visualization\n",
        "Since it is hard to visualize embeddings in a higher-dimensional space (when the embedding dimension $k > 3$), one approach is to project the embeddings to a lower dimensional space. T-SNE (T-distributed Stochastic Neighbor Embedding) is an algorithm that projects the embeddings while attempting to preserve their pariwise distances. It can be useful for visualization, but one should use it with care. For more information on using t-SNE, see [How to Use t-SNE Effectively](https://distill.pub/2016/misread-tsne/)."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "W6bkyeDao4uH",
        "colab": {}
      },
      "source": [
        "tsne_movie_embeddings(model_lowinit)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "y9j2Bbf8o4uI"
      },
      "source": [
        "You can highlight the embeddings of a given genre by clicking on the genres panel (SHIFT+click to select multiple genres).\n",
        "\n",
        "We can observe that the embeddings do not seem to have any notable structure, and the embeddings of a given genre are located all over the embedding space. This confirms the poor quality of the learned embeddings. One of the main reasons, which we will address in the next section, is that we only trained the model on observed pairs, and without regularization."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "oPmzSUHro4uI"
      },
      "source": [
        "# V. Regularization In Matrix Factorization\n",
        "\n",
        "In the previous section, our loss was defined as the mean squared error on the observed part of the rating matrix.  As discussed in the lecture, this can be problematic as the model does not learn how to place the embeddings of irrelevant movies. This phenomenon is known as *folding*.\n",
        "\n",
        "We will add regularization terms that will address this issue. We will use two types of regularization:\n",
        "- Regularization of the model parameters. This is a common $\\ell_2$ regularization term on the embedding matrices, given by $r(U, V) =  \\frac{1}{N} \\sum_i \\|U_i\\|^2 + \\frac{1}{M}\\sum_j \\|V_j\\|^2$.\n",
        "- A global prior that pushes the prediction of any pair towards zero, called the *gravity* term. This is given by $g(U, V) = \\frac{1}{MN} \\sum_{i = 1}^N \\sum_{j = 1}^M \\langle U_i, V_j \\rangle^2$.\n",
        "\n",
        "The total loss is then given by\n",
        "$$\n",
        "\\frac{1}{|\\Omega|}\\sum_{(i, j) \\in \\Omega} (A_{ij} - \\langle U_i, V_j\\rangle)^2 + \\lambda _r r(U, V) + \\lambda_g g(U, V)\n",
        "$$\n",
        "where $\\lambda_r$ and $\\lambda_g$ are two regularization coefficients (hyper-parameters)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Jz5bqVbFo4uJ"
      },
      "source": [
        "### Exercise 6: Build a regularized Matrix Factorization model and train it\n",
        "Write a function that builds a regularized model. You are given a function `gravity(U, V)` that computes the gravity term given the two embedding matrices $U$ and $V$.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "TBv8X-fYo4uK",
        "colab": {}
      },
      "source": [
        "def gravity(U, V):\n",
        "  \"\"\"Creates a gravity loss given two embedding matrices.\"\"\"\n",
        "  return 1. / (U.shape[0].value*V.shape[0].value) * tf.reduce_sum(\n",
        "      tf.matmul(U, U, transpose_a=True) * tf.matmul(V, V, transpose_a=True))\n",
        "\n",
        "def build_regularized_model(\n",
        "    ratings, embedding_dim=3, regularization_coeff=.1, gravity_coeff=1.,\n",
        "    init_stddev=0.1):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings: the DataFrame of movie ratings.\n",
        "    embedding_dim: The dimension of the embedding space.\n",
        "    regularization_coeff: The regularization coefficient lambda.\n",
        "    gravity_coeff: The gravity regularization coefficient lambda_g.\n",
        "  Returns:\n",
        "    A CFModel object that uses a regularized loss.\n",
        "  \"\"\"\n",
        "  # Split the ratings DataFrame into train and test.\n",
        "  train_ratings, test_ratings = split_dataframe(ratings)\n",
        "  # SparseTensor representation of the train and test datasets.\n",
        "  A_train = build_rating_sparse_tensor(train_ratings)\n",
        "  A_test = build_rating_sparse_tensor(test_ratings)\n",
        "  U = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[0], embedding_dim], stddev=init_stddev))\n",
        "  V = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[1], embedding_dim], stddev=init_stddev))\n",
        "\n",
        "  # ========================= Complete this section ============================\n",
        "  # error_train =\n",
        "  # error_test =\n",
        "  # gravity_loss =\n",
        "  # regularization_loss =\n",
        "  # ============================================================================\n",
        "  total_loss = error_train + regularization_loss + gravity_loss\n",
        "  losses = {\n",
        "      'train_error': error_train,\n",
        "      'test_error': error_test,\n",
        "  }\n",
        "  loss_components = {\n",
        "      'observed_loss': error_train,\n",
        "      'regularization_loss': regularization_loss,\n",
        "      'gravity_loss': gravity_loss,\n",
        "  }\n",
        "  embeddings = {\"user_id\": U, \"movie_id\": V}\n",
        "\n",
        "  return CFModel(embeddings, total_loss, [losses, loss_components])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "fhkmyFz8o4uL",
        "colab": {}
      },
      "source": [
        "# @title Solution\n",
        "def gravity(U, V):\n",
        "  \"\"\"Creates a gravity loss given two embedding matrices.\"\"\"\n",
        "  return 1. / (U.shape[0].value*V.shape[0].value) * tf.reduce_sum(\n",
        "      tf.matmul(U, U, transpose_a=True) * tf.matmul(V, V, transpose_a=True))\n",
        "\n",
        "def build_regularized_model(\n",
        "    ratings, embedding_dim=3, regularization_coeff=.1, gravity_coeff=1.,\n",
        "    init_stddev=0.1):\n",
        "  \"\"\"\n",
        "  Args:\n",
        "    ratings: the DataFrame of movie ratings.\n",
        "    embedding_dim: The dimension of the embedding space.\n",
        "    regularization_coeff: The regularization coefficient lambda.\n",
        "    gravity_coeff: The gravity regularization coefficient lambda_g.\n",
        "  Returns:\n",
        "    A CFModel object that uses a regularized loss.\n",
        "  \"\"\"\n",
        "  # Split the ratings DataFrame into train and test.\n",
        "  train_ratings, test_ratings = split_dataframe(ratings)\n",
        "  # SparseTensor representation of the train and test datasets.\n",
        "  A_train = build_rating_sparse_tensor(train_ratings)\n",
        "  A_test = build_rating_sparse_tensor(test_ratings)\n",
        "  U = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[0], embedding_dim], stddev=init_stddev))\n",
        "  V = tf.Variable(tf.random_normal(\n",
        "      [A_train.dense_shape[1], embedding_dim], stddev=init_stddev))\n",
        "\n",
        "  error_train = sparse_mean_square_error(A_train, U, V)\n",
        "  error_test = sparse_mean_square_error(A_test, U, V)\n",
        "  gravity_loss = gravity_coeff * gravity(U, V)\n",
        "  regularization_loss = regularization_coeff * (\n",
        "      tf.reduce_sum(U*U)/U.shape[0].value + tf.reduce_sum(V*V)/V.shape[0].value)\n",
        "  total_loss = error_train + regularization_loss + gravity_loss\n",
        "  losses = {\n",
        "      'train_error_observed': error_train,\n",
        "      'test_error_observed': error_test,\n",
        "  }\n",
        "  loss_components = {\n",
        "      'observed_loss': error_train,\n",
        "      'regularization_loss': regularization_loss,\n",
        "      'gravity_loss': gravity_loss,\n",
        "  }\n",
        "  embeddings = {\"user_id\": U, \"movie_id\": V}\n",
        "\n",
        "  return CFModel(embeddings, total_loss, [losses, loss_components])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "Pls1FspbFpzl",
        "colab_type": "text"
      },
      "source": [
        "It is now time to train the regularized model! You can try different values of the regularization coefficients, and different embedding dimensions."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "fgtnpletSjVg",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "reg_model = build_regularized_model(\n",
        "    ratings, regularization_coeff=0.1, gravity_coeff=1.0, embedding_dim=35,\n",
        "    init_stddev=.05)\n",
        "reg_model.train(num_iterations=2000, learning_rate=20.)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "ChIWbjRRo4uQ"
      },
      "source": [
        "Observe that adding the regularization terms results in a higher MSE, both on the training and test set. However, as we will see, the quality of the recommendations improves. This highlights a tension between fitting the observed data and minimizing the regularization terms. Fitting the observed data often emphasizes learning high similarity (between items with many interactions), but a good embedding representation also requires learning low similarity (between items with few or no interactions)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Fqumfb5bo4uQ"
      },
      "source": [
        "### Inspect the results\n",
        "Let's see if the results with regularization look better."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "VOhUY34ao4uQ",
        "colab": {}
      },
      "source": [
        "user_recommendations(reg_model, DOT, exclude_rated=True, k=10)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "cnL9h2pco4uR"
      },
      "source": [
        "Hopefully, these recommendations look better. You can change the similarity measure from COSINE to DOT and observe how this affects the recommendations.\n",
        "\n",
        "Since the model is likely to recommend items that you rated highly, you have the option to exclude the items you rated, using `exclude_rated=True`.\n",
        "\n",
        "In the following cells, we display the nearest neighbors, the embedding norms, and the t-SNE projection of the movie embeddings."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "NPByZUTPo4uR",
        "colab": {}
      },
      "source": [
        "movie_neighbors(reg_model, \"Aladdin\", DOT)\n",
        "movie_neighbors(reg_model, \"Aladdin\", COSINE)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "iiL6mZcpo4uY"
      },
      "source": [
        "Here we compare the embedding norms for `model` and `reg_model`. Selecting a subset of the embeddings will highlight them on both charts simultaneously."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "StMo4lDmLqpc",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "movie_embedding_norm([model, model_lowinit, reg_model])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "9staddTOo4uZ",
        "colab": {}
      },
      "source": [
        "# Visualize the embeddings\n",
        "tsne_movie_embeddings(reg_model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "moCS2-Dfo4ua"
      },
      "source": [
        "We should observe that the embeddings have a lot more structure than the unregularized case. Try selecting different genres and observe how they tend to form clusters (for example Horror, Animation and Children).\n",
        "\n",
        "### Conclusion\n",
        "This concludes this section on matrix factorization models. Note that while the scale of the problem is small enough to allow efficient training using SGD, many practical problems need to be trained using more specialized algorithms such as Alternating Least Squares (see [tf.contrib.factorization.WALSMatrixFactorization](https://www.tensorflow.org/api_docs/python/tf/contrib/factorization/WALSMatrixFactorization) for a TF implementation)."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "K7NJT9gbo4ub"
      },
      "source": [
        "# VI. Softmax model\n",
        "\n",
        "In this section, we will train a simple softmax model that predicts whether a given user has rated a movie.\n",
        "\n",
        "**Note**: if you are taking the self-study version of the class, make sure to read through the part of the class covering Softmax training before working on this part.\n",
        "\n",
        "The model will take as input a feature vector $x$ representing the list of movies the user has rated. We start from the ratings DataFrame, which we group by user_id."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "JJcaNiWdo4ub",
        "colab": {}
      },
      "source": [
        "rated_movies = (ratings[[\"user_id\", \"movie_id\"]]\n",
        "                .groupby(\"user_id\", as_index=False)\n",
        "                .aggregate(lambda x: list(x)))\n",
        "rated_movies.head()"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "X14ABp0Jo4uc"
      },
      "source": [
        "We then create a function that generates an example batch, such that each example contains the following features:\n",
        "- movie_id: A tensor of strings of the movie ids that the user rated.\n",
        "- genre: A tensor of strings of the genres of those movies\n",
        "- year: A tensor of strings of the release year."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "both",
        "id": "N_IsDAEAo4ud",
        "colab": {}
      },
      "source": [
        "#@title Batch generation code (run this cell)\n",
        "years_dict = {\n",
        "    movie: year for movie, year in zip(movies[\"movie_id\"], movies[\"year\"])\n",
        "}\n",
        "genres_dict = {\n",
        "    movie: genres.split('-')\n",
        "    for movie, genres in zip(movies[\"movie_id\"], movies[\"all_genres\"])\n",
        "}\n",
        "\n",
        "def make_batch(ratings, batch_size):\n",
        "  \"\"\"Creates a batch of examples.\n",
        "  Args:\n",
        "    ratings: A DataFrame of ratings such that examples[\"movie_id\"] is a list of\n",
        "      movies rated by a user.\n",
        "    batch_size: The batch size.\n",
        "  \"\"\"\n",
        "  def pad(x, fill):\n",
        "    return pd.DataFrame.from_dict(x).fillna(fill).values\n",
        "\n",
        "  movie = []\n",
        "  year = []\n",
        "  genre = []\n",
        "  label = []\n",
        "  for movie_ids in ratings[\"movie_id\"].values:\n",
        "    movie.append(movie_ids)\n",
        "    genre.append([x for movie_id in movie_ids for x in genres_dict[movie_id]])\n",
        "    year.append([years_dict[movie_id] for movie_id in movie_ids])\n",
        "    label.append([int(movie_id) for movie_id in movie_ids])\n",
        "  features = {\n",
        "      \"movie_id\": pad(movie, \"\"),\n",
        "      \"year\": pad(year, \"\"),\n",
        "      \"genre\": pad(genre, \"\"),\n",
        "      \"label\": pad(label, -1)\n",
        "  }\n",
        "  batch = (\n",
        "      tf.data.Dataset.from_tensor_slices(features)\n",
        "      .shuffle(1000)\n",
        "      .repeat()\n",
        "      .batch(batch_size)\n",
        "      .make_one_shot_iterator()\n",
        "      .get_next())\n",
        "  return batch\n",
        "\n",
        "def select_random(x):\n",
        "  \"\"\"Selectes a random elements from each row of x.\"\"\"\n",
        "  def to_float(x):\n",
        "    return tf.cast(x, tf.float32)\n",
        "  def to_int(x):\n",
        "    return tf.cast(x, tf.int64)\n",
        "  batch_size = tf.shape(x)[0]\n",
        "  rn = tf.range(batch_size)\n",
        "  nnz = to_float(tf.count_nonzero(x >= 0, axis=1))\n",
        "  rnd = tf.random_uniform([batch_size])\n",
        "  ids = tf.stack([to_int(rn), to_int(nnz * rnd)], axis=1)\n",
        "  return to_int(tf.gather_nd(x, ids))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Yef5q1Qlo4ue"
      },
      "source": [
        "### Loss function\n",
        "Recall that the softmax model maps the input features $x$ to a user embedding $\\psi(x) \\in \\mathbb R^d$, where $d$ is the embedding dimension. This vector is then multiplied by a movie embedding matrix $V \\in \\mathbb R^{m \\times d}$ (where $m$ is the number of movies), and the final output of the model is the softmax of the product\n",
        "$$\n",
        "\\hat p(x) = \\text{softmax}(\\psi(x) V^\\top).\n",
        "$$\n",
        "Given a target label $y$, if we denote by $p = 1_y$ a one-hot encoding of this target label, then the loss is the cross-entropy between $\\hat p(x)$ and $p$."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "DDnGAN_0o4ue"
      },
      "source": [
        "### Exercise 7: Write a loss function for the softmax model.\n",
        "\n",
        "In this exercise, we will write a function that takes tensors representing the user embeddings $\\psi(x)$, movie embeddings $V$, target label $y$, and return the cross-entropy loss.\n",
        "\n",
        "Hint: You can use the function [`tf.nn.sparse_softmax_cross_entropy_with_logits`](https://www.tensorflow.org/api_docs/python/tf/nn/sparse_softmax_cross_entropy_with_logits), which takes `logits` as input, where `logits` refers to the product $\\psi(x) V^\\top$."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "4OKzworlo4ue",
        "colab": {}
      },
      "source": [
        "def softmax_loss(user_embeddings, movie_embeddings, labels):\n",
        "  \"\"\"Returns the cross-entropy loss of the softmax model.\n",
        "  Args:\n",
        "    user_embeddings: A tensor of shape [batch_size, embedding_dim].\n",
        "    movie_embeddings: A tensor of shape [num_movies, embedding_dim].\n",
        "    labels: A sparse tensor of dense_shape [batch_size, 1], such that\n",
        "      labels[i] is the target label for example i.\n",
        "  Returns:\n",
        "    The mean cross-entropy loss.\n",
        "  \"\"\"\n",
        "  # ========================= Complete this section ============================\n",
        "  # logits =\n",
        "  # loss =\n",
        "  # ============================================================================\n",
        "  return loss"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "hQNuR42eo4uf",
        "colab": {}
      },
      "source": [
        "# @title Solution\n",
        "def softmax_loss(user_embeddings, movie_embeddings, labels):\n",
        "  \"\"\"Returns the cross-entropy loss of the softmax model.\n",
        "  Args:\n",
        "    user_embeddings: A tensor of shape [batch_size, embedding_dim].\n",
        "    movie_embeddings: A tensor of shape [num_movies, embedding_dim].\n",
        "    labels: A tensor of [batch_size], such that labels[i] is the target label\n",
        "      for example i.\n",
        "  Returns:\n",
        "    The mean cross-entropy loss.\n",
        "  \"\"\"\n",
        "  # Verify that the embddings have compatible dimensions\n",
        "  user_emb_dim = user_embeddings.shape[1].value\n",
        "  movie_emb_dim = movie_embeddings.shape[1].value\n",
        "  if user_emb_dim != movie_emb_dim:\n",
        "    raise ValueError(\n",
        "        \"The user embedding dimension %d should match the movie embedding \"\n",
        "        \"dimension % d\" % (user_emb_dim, movie_emb_dim))\n",
        "\n",
        "  logits = tf.matmul(user_embeddings, movie_embeddings, transpose_b=True)\n",
        "  loss = tf.reduce_mean(tf.nn.sparse_softmax_cross_entropy_with_logits(\n",
        "      logits=logits, labels=labels))\n",
        "  return loss"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "Y9SvjO4go4ug"
      },
      "source": [
        "### Exercise 8: Build a softmax model, train it, and inspect its embeddings.\n",
        "\n",
        "We are now ready to build a softmax CFModel. Complete the `build_softmax_model` function in the next cell. The architecture of the model is defined in the function `create_user_embeddings` and illustrated in the figure below. The input embeddings (movie_id, genre and year) are concatenated to form the input layer, then we have hidden layers with dimensions specified by the `hidden_dims` argument. Finally, the last hidden layer is multiplied by the movie embeddings to obtain the logits layer. For the target label, we will use a randomly-sampled movie_id from the list of movies the user rated.\n",
        "\n",
        "![Softmax model](https://github.com/google/eng-edu/blob/master/ml/recommendation-systems/images/softmax-model.png?raw=true)\n",
        "\n",
        "Complete the function below by creating the feature columns and embedding columns, then creating the loss tensors both for the train and test sets (using the `softmax_loss` function of the previous exercise).\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "FVa794-zbE5q",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def build_softmax_model(rated_movies, embedding_cols, hidden_dims):\n",
        "  \"\"\"Builds a Softmax model for MovieLens.\n",
        "  Args:\n",
        "    rated_movies: DataFrame of traing examples.\n",
        "    embedding_cols: A dictionary mapping feature names (string) to embedding\n",
        "      column objects. This will be used in tf.feature_column.input_layer() to\n",
        "      create the input layer.\n",
        "    hidden_dims: int list of the dimensions of the hidden layers.\n",
        "  Returns:\n",
        "    A CFModel object.\n",
        "  \"\"\"\n",
        "  def create_network(features):\n",
        "    \"\"\"Maps input features dictionary to user embeddings.\n",
        "    Args:\n",
        "      features: A dictionary of input string tensors.\n",
        "    Returns:\n",
        "      outputs: A tensor of shape [batch_size, embedding_dim].\n",
        "    \"\"\"\n",
        "    # Create a bag-of-words embedding for each sparse feature.\n",
        "    inputs = tf.feature_column.input_layer(features, embedding_cols)\n",
        "    # Hidden layers.\n",
        "    input_dim = inputs.shape[1].value\n",
        "    for i, output_dim in enumerate(hidden_dims):\n",
        "      w = tf.get_variable(\n",
        "          \"hidden%d_w_\" % i, shape=[input_dim, output_dim],\n",
        "          initializer=tf.truncated_normal_initializer(\n",
        "              stddev=1./np.sqrt(output_dim))) / 10.\n",
        "      outputs = tf.matmul(inputs, w)\n",
        "      input_dim = output_dim\n",
        "      inputs = outputs\n",
        "    return outputs\n",
        "\n",
        "  train_rated_movies, test_rated_movies = split_dataframe(rated_movies)\n",
        "  train_batch = make_batch(train_rated_movies, 200)\n",
        "  test_batch = make_batch(test_rated_movies, 100)\n",
        "\n",
        "  with tf.variable_scope(\"model\", reuse=False):\n",
        "    # Train\n",
        "    train_user_embeddings = create_network(train_batch)\n",
        "    train_labels = select_random(train_batch[\"label\"])\n",
        "  with tf.variable_scope(\"model\", reuse=True):\n",
        "    # Test\n",
        "    test_user_embeddings = create_network(test_batch)\n",
        "    test_labels = select_random(test_batch[\"label\"])\n",
        "    movie_embeddings = tf.get_variable(\n",
        "        \"input_layer/movie_id_embedding/embedding_weights\")\n",
        "\n",
        "  # ========================= Complete this section ============================\n",
        "  # train_loss =\n",
        "  # test_loss =\n",
        "  # test_precision_at_10 =\n",
        "  # ============================================================================\n",
        "\n",
        "  metrics = (\n",
        "      {\"train_loss\": train_loss, \"test_loss\": test_loss},\n",
        "      {\"test_precision_at_10\": test_precision_at_10}\n",
        "  )\n",
        "  embeddings = {\"movie_id\": movie_embeddings}\n",
        "  return CFModel(embeddings, train_loss, metrics)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "cellView": "form",
        "id": "zAAr73xno4uj",
        "colab": {}
      },
      "source": [
        "# @title Solution\n",
        "\n",
        "def build_softmax_model(rated_movies, embedding_cols, hidden_dims):\n",
        "  \"\"\"Builds a Softmax model for MovieLens.\n",
        "  Args:\n",
        "    rated_movies: DataFrame of traing examples.\n",
        "    embedding_cols: A dictionary mapping feature names (string) to embedding\n",
        "      column objects. This will be used in tf.feature_column.input_layer() to\n",
        "      create the input layer.\n",
        "    hidden_dims: int list of the dimensions of the hidden layers.\n",
        "  Returns:\n",
        "    A CFModel object.\n",
        "  \"\"\"\n",
        "  def create_network(features):\n",
        "    \"\"\"Maps input features dictionary to user embeddings.\n",
        "    Args:\n",
        "      features: A dictionary of input string tensors.\n",
        "    Returns:\n",
        "      outputs: A tensor of shape [batch_size, embedding_dim].\n",
        "    \"\"\"\n",
        "    # Create a bag-of-words embedding for each sparse feature.\n",
        "    inputs = tf.feature_column.input_layer(features, embedding_cols)\n",
        "    # Hidden layers.\n",
        "    input_dim = inputs.shape[1].value\n",
        "    for i, output_dim in enumerate(hidden_dims):\n",
        "      w = tf.get_variable(\n",
        "          \"hidden%d_w_\" % i, shape=[input_dim, output_dim],\n",
        "          initializer=tf.truncated_normal_initializer(\n",
        "              stddev=1./np.sqrt(output_dim))) / 10.\n",
        "      outputs = tf.matmul(inputs, w)\n",
        "      input_dim = output_dim\n",
        "      inputs = outputs\n",
        "    return outputs\n",
        "\n",
        "  train_rated_movies, test_rated_movies = split_dataframe(rated_movies)\n",
        "  train_batch = make_batch(train_rated_movies, 200)\n",
        "  test_batch = make_batch(test_rated_movies, 100)\n",
        "\n",
        "  with tf.variable_scope(\"model\", reuse=False):\n",
        "    # Train\n",
        "    train_user_embeddings = create_network(train_batch)\n",
        "    train_labels = select_random(train_batch[\"label\"])\n",
        "  with tf.variable_scope(\"model\", reuse=True):\n",
        "    # Test\n",
        "    test_user_embeddings = create_network(test_batch)\n",
        "    test_labels = select_random(test_batch[\"label\"])\n",
        "    movie_embeddings = tf.get_variable(\n",
        "        \"input_layer/movie_id_embedding/embedding_weights\")\n",
        "\n",
        "  test_loss = softmax_loss(\n",
        "      test_user_embeddings, movie_embeddings, test_labels)\n",
        "  train_loss = softmax_loss(\n",
        "      train_user_embeddings, movie_embeddings, train_labels)\n",
        "  _, test_precision_at_10 = tf.metrics.precision_at_k(\n",
        "      labels=test_labels,\n",
        "      predictions=tf.matmul(test_user_embeddings, movie_embeddings, transpose_b=True),\n",
        "      k=10)\n",
        "\n",
        "  metrics = (\n",
        "      {\"train_loss\": train_loss, \"test_loss\": test_loss},\n",
        "      {\"test_precision_at_10\": test_precision_at_10}\n",
        "  )\n",
        "  embeddings = {\"movie_id\": movie_embeddings}\n",
        "  return CFModel(embeddings, train_loss, metrics)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "VZB1J8l9o4ul"
      },
      "source": [
        "### Train the Softmax model\n",
        "\n",
        "We are now ready to train the softmax model. You can set the following hyperparameters:\n",
        "- learning rate\n",
        "- number of iterations. Note: you can run `softmax_model.train()` again to continue training the model from its current state.\n",
        "- input embedding dimensions (the `input_dims` argument)\n",
        "- number of hidden layers and size of each layer (the `hidden_dims` argument)\n",
        "\n",
        "Note: since our input features are string-valued (movie_id, genre, and year), we need to map them to integer ids. This is done using [`tf.feature_column.categorical_column_with_vocabulary_list`](https://www.tensorflow.org/api_docs/python/tf/feature_column/categorical_column_with_vocabulary_list), which takes a vocabulary list specifying all the values the feature can take. Then each id is mapped to an embedding vector using [`tf.feature_column.embedding_column`](https://www.tensorflow.org/api_docs/python/tf/feature_column/embedding_column).\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "jJsXAS_go4ul",
        "colab": {}
      },
      "source": [
        "# Create feature embedding columns\n",
        "def make_embedding_col(key, embedding_dim):\n",
        "  categorical_col = tf.feature_column.categorical_column_with_vocabulary_list(\n",
        "      key=key, vocabulary_list=list(set(movies[key].values)), num_oov_buckets=0)\n",
        "  return tf.feature_column.embedding_column(\n",
        "      categorical_column=categorical_col, dimension=embedding_dim,\n",
        "      # default initializer: trancated normal with stddev=1/sqrt(dimension)\n",
        "      combiner='mean')\n",
        "\n",
        "with tf.Graph().as_default():\n",
        "  softmax_model = build_softmax_model(\n",
        "      rated_movies,\n",
        "      embedding_cols=[\n",
        "          make_embedding_col(\"movie_id\", 35),\n",
        "          make_embedding_col(\"genre\", 3),\n",
        "          make_embedding_col(\"year\", 2),\n",
        "      ],\n",
        "      hidden_dims=[35])\n",
        "\n",
        "softmax_model.train(\n",
        "    learning_rate=8., num_iterations=3000, optimizer=tf.train.AdagradOptimizer)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "-sYjuHxJo4un"
      },
      "source": [
        "### Inspect the embeddings\n",
        "\n",
        "We can inspect the movie embeddings as we did for the previous models. Note that in this case, the movie embeddings are used at the same time as input embeddings (for the bag of words representation of the user history), and as softmax weights."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "mvJazlnMo4uo",
        "colab": {}
      },
      "source": [
        "movie_neighbors(softmax_model, \"Aladdin\", DOT)\n",
        "movie_neighbors(softmax_model, \"Aladdin\", COSINE)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "ReIP69-9o4ur",
        "colab": {}
      },
      "source": [
        "movie_embedding_norm([reg_model, softmax_model])"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab_type": "code",
        "id": "Trq0yYrXo4us",
        "colab": {}
      },
      "source": [
        "tsne_movie_embeddings(softmax_model)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "colab_type": "text",
        "id": "fZkZJ8yco4uu"
      },
      "source": [
        "## Congratulations!\n",
        "\n",
        "You have completed this Colab notebook.\n",
        "\n",
        "If you would like to further explore these models, we encourage you to try different hyperparameters and observe how this affects the quality of the model and the structure of the embedding space. Here are some suggestions:\n",
        "- Change the embedding dimension.\n",
        "- In the softmax model: change the number of hidden layers, and the input features. For example, you can try a model with no hidden layers, and only the movie ids as inputs.\n",
        "- Using other similarity measures: In this Colab notebook, we used dot product $d(u, V_j) = \\langle u, V_j \\rangle$ and cosine $d(u, V_j) = \\frac{\\langle u, V_j \\rangle}{\\|u\\|\\|V_j\\|}$, and discussed how the norms of the embeddings affect the recommendations. You can also try other variants which apply a transformation to the norm, for example $d(u, V_j) = \\frac{\\langle u, V_j \\rangle}{\\|V_j\\|^\\alpha}$."
      ]
    }
  ]
}
